#include "TexturePacker.hpp"

namespace fge
{

TexturePacker::TexturePacker(int padding)
	: padding(padding), root(0)
{
}

TexturePacker::~TexturePacker()
{
	FreeNode(root);
}

void TexturePacker::AddTexture(int width, int height)
{
	Node node;
	node.width = width + padding * 2;
	node.height = height + padding * 2;
	node.index = textures.size();
	textures.push_back(node);
}

// todo: sorting options
bool CompareNodes(const Node &lhs, const Node &rhs)
{
//	return lhs.width * lhs.height > rhs.width * rhs.height;

	if(lhs.height == rhs.height)
		return lhs.width > rhs.width;
	return lhs.height > rhs.height;
}

void TexturePacker::PackTextures(int &textureWidth, int &textureHeight)
{
	int currentSize = 4;
	do
	{
		currentSize *= 2;
	} while(!TryPackTextures(currentSize, currentSize));

	textureWidth = textureHeight = currentSize;
}

void TexturePacker::GetDataByIndex(int index, int &x, int &y, int &width, int &height)
{
	Node *node = GetNodeByIndex(root, index);
	x = node->x + padding;
	y = node->y + padding;
	width = node->width - padding * 2;
	height = node->height - padding * 2;
}

bool TexturePacker::TryPackTextures(int textureWidth, int textureHeight)
{
	textures.sort(&CompareNodes);
	FreeNode(root);

	root = new Node;
	root->width = textureWidth;
	root->height = textureHeight;
	root->index = -1;
	root->left = NULL;
	root->right = NULL;
	root->x = 0;
	root->y = 0;

	for(std::list<Node>::iterator iterator=textures.begin(); iterator != textures.end(); ++iterator)
	{
		if(!InsertTexture(root, &(*iterator)))
			return false;
	}

	return true;
}

void TexturePacker::FreeNode(Node *node)
{
	if(node == NULL)
		return;
	FreeNode(node->left);
	delete node->left;
	FreeNode(node->right);
	delete node->right;
}

bool TexturePacker::InsertTexture(Node *node, Node *texture)
{
	if(node == NULL)
		return false;

	if(node->index == -1)
	{
		if(texture->width > node->width || texture->height > node->height)
			return false;

		if(node->width == texture->width && node->height == texture->height)
		{
			node->index = texture->index;
			return true;
		}

		if(node->width != texture->width)
		{
			node->left = new Node;
			node->left->width = node->width - texture->width;
			node->left->height = texture->height;
			node->left->index = -1;
			node->left->left = NULL;
			node->left->right = NULL;
			node->left->x = node->x + texture->width;
			node->left->y = node->y;
		}

		if(node->height != texture->height)
		{
			node->right = new Node;
			node->right->width = node->width;
			node->right->height = node->height - texture->height;
			node->right->index = -1;
			node->right->left = NULL;
			node->right->right = NULL;
			node->right->x = node->x;
			node->right->y = node->y + texture->height;
		}

		node->width = texture->width;
		node->height = texture->height;
		node->index = texture->index;

		return true;
	}
	else if(InsertTexture(node->left, texture))
		return true;
	else
		return InsertTexture(node->right, texture);
}

Node* TexturePacker::GetNodeByIndex(Node *node, int index)
{
	if(node == NULL)
		return NULL;

	if(node->index == index)
		return node;

	Node *left = GetNodeByIndex(node->left, index);
	if(left != NULL)
		return left;
	return GetNodeByIndex(node->right, index);
}

}
